#! /usr/bin/env python

# Alunos:   Eliezer de Souza da Silva  RA: 124065
#           Fernanda Brandao Silva     RA: 060727
#           Michel Silva Fornaciali    RA: 071884
# IA368R: Eduardo Valle - Trabalho 2, Programa 2 - kmeans

from random import sample
from numpy import array,dot,sqrt, argmin, mean, argwhere, savetxt, loadtxt
import matplotlib,sys, os
import matplotlib.pyplot as plt
from scipy.spatial.distance import cdist

def dist_l2(v,w):
#euclidean distance of two arrays v1 and v2
    return sqrt(dot(v-w,v-w))

def kmeans(points, k):
#points is a list of array with n items, k is positive integer > 2
    n= len(points)
    if( (n < k) or (n < 1) or (k < 1) ):
        return
    
    points = array(points)
    
    centers_index = sample(range(n),k)
    centers_point= points[centers_index, :]

    continua = True
    while (continua):
        continua = False
        
        #assignment step: calculate the distance from each point to each center
        distances_to_centers = cdist(points, centers_point, 'euclidean')
	# and assin it this nearest center
        assignments = argmin(distances_to_centers, axis=1)
        
        for i in range(k):
            # calculate new centers-points based on the mean of the assigned points to a given center
            group_of_points = argwhere(assignments==i)[:,0]
            if group_of_points.size>0:
                centers_mean_acc = mean(points[group_of_points,:], axis=0)
            
                if(dist_l2(centers_point[i],centers_mean_acc) > 0.001):
                    continua = True
                centers_point[i] = centers_mean_acc
    
    return centers_point,assignments


def print_points(fp,points):
    for point in points:
        fp.write(" ".join(str(int(x)) for x in point)+"\n")
